//给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 
//
// 示例 1: 
//
// 输入: 1->2->3->4->5->NULL, k = 2
//输出: 4->5->1->2->3->NULL
//解释:
//向右旋转 1 步: 5->1->2->3->4->NULL
//向右旋转 2 步: 4->5->1->2->3->NULL
// 
//
// 示例 2: 
//
// 输入: 0->1->2->NULL, k = 4
//输出: 2->0->1->NULL
//解释:
//向右旋转 1 步: 2->0->1->NULL
//向右旋转 2 步: 1->2->0->NULL
//向右旋转 3 步: 0->1->2->NULL
//向右旋转 4 步: 2->0->1->NULL 
// Related Topics 链表 双指针 
// 👍 322 👎 0

package leetcode.editor.cn;

//Java：旋转链表
public class P61RotateList {

    /*
     * 思路：观察  1->2->3->4->5->NULL，k=2，其实就是求倒二个的结点，然后最后一个结点后面拼上头结点就行了
     *
     * 执行用时： 1 ms , 在所有 Java 提交中击败了 89.31% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 25.21% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    class Solution {
        // 注释以这个测试用例为例子
        // 输入: 1->2->3->4->5->NULL, k = 2
        // 输出: 4->5->1->2->3->NULL
        public ListNode rotateRight(ListNode head, int k) {
            ListNode resultNode = head;
            int len = getLength(head);
            if (len == 0 || k == 0) {
                return resultNode;
            }
            k = len - k % len;        // k=3
            if (k != 0 && k != len) {
                // 头结点 1 保留一份
                ListNode tempHead = head;

                // 循环，head此时在 3
                for (int i = 1; i < k; i++) {
                    head = head.next;
                }

                // midNode 在 4
                ListNode midNode = head.next;
                head.next = null;

                // 找出最后一个midNode 5
                ListNode finalNode = midNode;
                while (finalNode.next != null) {
                    finalNode = finalNode.next;
                }

                // 将一开始的 1 接到5 后面
                finalNode.next = tempHead;

                // 返回 4结点
                resultNode = midNode;
            }
            return resultNode;
        }

        private int getLength(ListNode head) {
            if (head == null) {
                return 0;
            }

            int i = 1;
            ListNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
                i++;
            }
            return i;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P61RotateList().new Solution();
        ListNode node1 = new ListNode(1);
        node1 = solution.rotateRight(node1, 1);
        System.out.println(node1);
        // TO TEST
    }

    private static ListNode add(ListNode listNode, int x) {
        ListNode node = new ListNode(x);
        node.next = listNode;
        return node;
    }

}